package sort;

/**
 * @Author: Hugh @Date: 2021/3/1
 */
public class QuickSort {

    public static void quickSort(int[] source, int left, int right) {
        if (source.length <= 1 || left > right){
            return;
        }
        int base = source[left];
        int i = left;
        int j = right;
        while(i < j){
            while(source[j] >= base && i < j){
                j--;
            }
            while(source[i] <= base && i < j){
                i++;
            }
            //swap 一定要在i<j的时候进行交换
            if(i < j ){
                swap(source, i, j);
            }
        }
        //find
        source[left] = source[i];
        source[i] = base;
        quickSort(source, left, i-1);
        quickSort(source, i+1, right);
    }

    private static void swap(int[] target, int i, int j) {
        int temp = target[i];
        target[i] = target[j];
        target[j] = temp;
    }

    public static void main(String[] args) {
        System.out.println("--------------------");
        int[] arr = {867,34,1,345,867,745,568,8};
        quickSort(arr, 0, arr.length-1);
        for (int i = arr.length - 1; i >= 0; i--) {
            System.out.print(arr[i] + "  ");
        }
        System.out.println();
        System.out.println("---------------------");

    }
}
